package zuochengyun;

import java.util.List;

/**
 * Created by shuowu on 2017/9/27.
 * 超过三分之一的数
 */
public class MoreThanOneThirdNumber {

    public static void main(String[] args) {
//        int[] nums = {1, 3, 2, 4, 6, 9, 3, 8, 3};
        int[] nums = {1, 3, 4, 4, 1, 3, 0, 1};
        int m = 0, n = 0; //最多存在2个出现次数超过 1/3 的元素
        int cm = 0, cn = 0; //对应 m 和 n 的统计
        for (int num : nums) {
            if (cm == 0 || num == m) {
                m = num;
                ++cm;
            } else if (cn == 0 || num == n) {
                n = num;
                ++cn;
            } else {
                --cm;
                --cn;
            }
        }

        System.out.println("m:" + m + " n:" + n);
        System.out.println("cm:" + cm + " cn:" + cn);
    }
}
